package main

import "fmt"

//我写的
//func letterCombinations(digits string) []string {
//	if len(digits) == 0 {
//		return []string{}
//	}
//	m := map[int]string{
//		2: "abc",
//		3: "def",
//		4: "ghi",
//		5: "jkl",
//		6: "mno",
//		7: "pqrs",
//		8: "tuv",
//		9: "wxyz",
//	}
//	var res []string
//	//fmt.Println(int(digits[0] - 48))
//	//fmt.Println(m[2])
//	for i := 0; i < len(m[int(digits[0]-48)]); i++ {
//		if len(digits) >= 2 {
//			for j := 0; j < len(m[int(digits[1]-48)]); j++ {
//				if len(digits) >= 3 {
//					for k := 0; k < len(m[int(digits[2]-48)]); k++ {
//						if len(digits) == 4 {
//							for l := 0; l < len(m[int(digits[3]-48)]); l++ {
//								res = append(res, string(m[int(digits[0]-48)][i])+string(m[int(digits[1]-48)][j])+string(m[int(digits[2]-48)][k])+string(m[int(digits[3]-48)][l]))
//							}
//						} else {
//							res = append(res, string(m[int(digits[0]-48)][i])+string(m[int(digits[1]-48)][j])+string(m[int(digits[2]-48)][k]))
//						}
//
//					}
//				} else {
//					res = append(res, string(m[int(digits[0]-48)][i])+string(m[int(digits[1]-48)][j]))
//				}
//
//			}
//		} else {
//			res = append(res, string(m[int(digits[0]-48)][i]))
//		}
//
//	}
//	return res
//
//}

// digitToLetters 映射数字到对应的字母字符串
var digitToLetters = map[rune]string{
	'2': "abc",
	'3': "def",
	'4': "ghi",
	'5': "jkl",
	'6': "mno",
	'7': "pqrs",
	'8': "tuv",
	'9': "wxyz",
}

// letterCombinations 函数用于生成给定数字字符串的所有字母组合
func letterCombinations(digits string) []string {
	var res []string // 用于存储最终的结果
	// 调用回溯函数进行组合生成
	backtrack(digits, "", &res)
	return res // 返回生成的结果
}

// backtrack 是回溯函数，用于递归生成字母组合
func backtrack(digits, current string, res *[]string) {
	// 如果数字字符串为空，说明完成了一次组合，将当前组合添加到结果中
	if len(digits) == 0 {
		*res = append(*res, current)
		return
	}
	digit := rune(digits[0])         // 获取当前数字字符
	letters := digitToLetters[digit] // 获取当前数字对应的字母字符串
	// 遍历当前数字对应的每个字母
	for _, letter := range letters {
		// 递归处理剩余的数字字符串，并将当前字母添加到当前组合中
		backtrack(digits[1:], current+string(letter), res)
	}
}

func main() {
	fmt.Println(letterCombinations("23"))
}
